// https://www.lintcode.com/problem/scramble-string/description
// 430. Scramble String
// Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

// Below is one possible representation of s1 = "great":

//     great
//    /    \
//   gr    eat
//  / \    /  \
// g   r  e   at
//            / \
//           a   t
// To scramble the string, we may choose any non-leaf node and swap its two children.

// For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

//     rgeat
//    /    \
//   rg    eat
//  / \    /  \
// r   g  e   at
//            / \
//           a   t
// We say that "rgeat" is a scrambled string of "great".

// Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

//     rgtae
//    /    \
//   rg    tae
//  / \    /  \
// r   g  ta  e
//        / \
//       t   a
// We say that "rgtae" is a scrambled string of "great".

// Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

// Example
// Example1

// Input:
// "great"
// "rgeat"
// Output:
// true
// Challenge
// O(n3) time



class Solution {
public:
    /**
     * @param s1: A string
     * @param s2: Another string
     * @return: whether s2 is a scrambled string of s1
     */
        // sort(s1.begin(), s1.end());
        // sort(s2.begin(), s2.end());
        // return s1 == s2; 必要不充分
        // Input
        // "abcd"
        // "bdac"
        // Output
        // true
        // Expected
        // false
        
        // 个：递推只要看最后就行了：要么ab=ab 要么ab=ba，不要被任务吓到;
        // 题目只转一次
        
        
    // 法一：递推+剪枝
    // bool isScramble(string s1, string s2) {
        // if (s1 == s2)
        // {
        //     return true;
        // }
        // if (s1.length() != s2.length())
        // {
        //     cout << "here1" << endl;
        //     return false; // 剪枝
        // }
        // string ss1 = s1;
        // string ss2 = s2;
        // sort(ss1.begin(), ss1.end());
        // sort(ss2.begin(), ss2.end());
        
        // if (ss1 != ss2)
        // {
        //     return false; 
        // }
        // for (int i = 1; i < s1.length(); ++i) 
        // // 注意从1开始，不能从0，死循环;
        // // 第二位表示长度，length能取到
        // {
        //     if((isScramble(s1.substr(0, i), s2.substr(0, i)) && 
        //     isScramble(s1.substr(i), s2.substr(i))) ||
        //     (isScramble(s1.substr(0, i),  s2.substr(s2.length() - i)) && 
        //     // isScramble(s1.substr(s1.length() - i), s2.substr(0, i))))
        //     isScramble(s1.substr(i), s2.substr(0, s2.length() - i))))
        //     {
        //         return true;
        //     }
        // }
        // return false;
    // }
    
    
    
     // 法二：记忆化搜索
    // map<string, bool> memo;
    // bool isScramble(string s1, string s2) {
    //     if (memo.find(s1 + "#" + s2) != memo.end())
    //     {
    //         return memo[s1 + "#" + s2];
    //     }
    //     if (s1.length() != s2.length())
    //     {
    //         return false;
    //     }
    //     if (s1.length() == 1)
    //     {
    //         return s1 == s2;
    //     }
    //     for (int i = 1; i < s1.length(); ++i) 
    //     {
    //         if((isScramble(s1.substr(0, i), s2.substr(0, i)) && 
    //         isScramble(s1.substr(i), s2.substr(i))) ||
    //         (isScramble(s1.substr(0, i),  s2.substr(s2.length() - i)) && 
    //         // isScramble(s1.substr(s1.length() - i), s2.substr(0, i))))
    //         isScramble(s1.substr(i), s2.substr(0, s2.length() - i))))
    //         {
    //             memo[s1 + "#" + s2] = true;
    //             return true;
    //         }
    //     }
    //     memo[s1 + "#" + s2] = false;
    //     return false;   
    // }
    
    // 法三：动态规划，注意数组里面存的东西
    bool isScramble(string s1, string s2) {
        int n = s1.length();
        if (s2.length() != n)
        {
            return false;
        }
        bool ***record = new bool**[n + 1];
        for (int i = 0; i <= n; ++i)
        {
            record[i] = new bool*[n];
        }
        for (int i = 0; i <= n; ++i)
        {
            for (int j = 0; j < n; ++j) 
            {
                record[i][j] = new bool[n];
                record[i][j][1] = (s1[i] == s2[j]);
            }
        }
        for (int len=2; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i)
            {
                for (int j = 0; j <= n - len; ++j)
                {
                    record[i][j][len] = false;
                    for (int w = 1; w < len; ++w)
                    {
                        if ((record[i][j][w] && record[i + w][j + w][len - w])
                        || (record[i][j + len - w][w] && record[i + w][j][len - w]))
                        {
                            record[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return record[0][0][n];
    }
};